package com.hui.testTree;


import org.apache.commons.collections.CollectionUtils;

import java.util.ArrayList;
import java.util.List;
import java.util.Map;

public class TreeUtil {

    private String ID = "id";
    private String PARENT_ID = "pid";
    private String CURRENT_LEVEL = "level";
    private String LEAF = "leaf";
    private String CHILDREN = "children";

    public TreeUtil() {
    }

    public TreeUtil(String id, String pid) {
        this.ID = id;
        this.PARENT_ID = pid;
    }

    @SuppressWarnings("unchecked")
    private List<Map> buildListToTree(List<Map> dirs) {
        List<Map> roots = findRoots(dirs);
        List<Map> notRoots = (List<Map>) CollectionUtils.subtract(dirs, roots);//非根节点
        for (Map root : roots) {
            root.put(CHILDREN, findChildren(root, notRoots));
        }
        return roots;
    }

    public List<Map> findRoots(List<Map> allNodes) {
        List<Map> results = new ArrayList<Map>();
        for (Map node : allNodes) {
            boolean isRoot = true;
            for (Map comparedOne : allNodes) {
                //判断是否是其它节点的子节点，如果不是子节点，那么就是根节点
                if (node.get(PARENT_ID) == comparedOne.get(ID)) {
                    isRoot = false;
                    break;
                }
            }
            if (isRoot) {
                node.put(CURRENT_LEVEL, 0);
                results.add(node);
            }
        }
        return results;
    }

    @SuppressWarnings("unchecked")
    private List<Map> findChildren(Map root, List<Map> notRoots) {
        List<Map> children = new ArrayList<Map>();
        for (Map comparedOne : notRoots) {
            if (comparedOne.get(PARENT_ID) == root.get(ID)) {
                comparedOne.put(CURRENT_LEVEL, (int) root.get(CURRENT_LEVEL) + 1);
                children.add(comparedOne);
            }
        }
        List<Map> notChildren = (List<Map>) CollectionUtils.subtract(notRoots, children);
        for (Map child : children) {
            List<Map> tmpChildren = findChildren(child, notChildren);//递归
            if (tmpChildren == null || tmpChildren.size() < 1) {
                child.put(LEAF, true);
            } else {
                child.put(LEAF, false);
            }
            child.put(CHILDREN, tmpChildren);
        }
        return children;
    }

//    /**
//     * 测试用
//     */
//    public static void main(String[] args) {
//        TreeUtil treeUtil = new TreeUtil();
//        List<Map> allNodes = new ArrayList<Map>();
//
//        Map node1 = new HashMap();
//        Map node2 = new HashMap();
//        Map node3 = new HashMap();
//        Map node4 = new HashMap();
//        Map node5 = new HashMap();
//        Map node6 = new HashMap();
//
//        node1.put("id", 1);
//        node1.put("pid", 0);
//        node2.put("id", 2);
//        node2.put("pid", 0);
//        node3.put("id", 3);
//        node3.put("pid", 0);
//        node4.put("id", 4);
//        node4.put("pid", 1);
//        node5.put("id", 5);
//        node5.put("pid", 1);
//        node6.put("id", 6);
//        node6.put("pid", 1);
//
//        allNodes.add(node1);
//        allNodes.add(node2);
//        allNodes.add(node3);
//        allNodes.add(node4);
//        allNodes.add(node5);
//        allNodes.add(node6);
//
//        List<Map> roots = treeUtil.buildListToTree(allNodes);
//        for (Map n : roots) {
//            System.out.println(n);
//        }
//
//    }
}
